<!doctype html>



  


<html class="theme-next pisces use-motion">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  
  
  <link href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />




  
  
  
  

  
    
    
  

  

  

  

  

  
    
    
    <link href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">
  






<link href="/vendors/font-awesome/css/font-awesome.min.css?v=4.4.0" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.0.1" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="排序,算法," />





  <link rel="alternate" href="/atom.xml" title="前端-洋洋" type="application/atom+xml" />




  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=5.0.1" />






<meta name="description" content="平常在项目中可能都会用到排序，就我本人而言，可能大部分都是用的选择排序或者冒泡排序，简单粗暴，但是这往往都只是实现了功能，而没有去关注性能，所以还是有必要了解常用的排序方法(使用内存)。
1.插入排序-直接插入排序基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要">
<meta property="og:type" content="article">
<meta property="og:title" content="排序算法">
<meta property="og:url" content="http://html-js.site/2016/05/20/排序算法/index.html">
<meta property="og:site_name" content="前端-洋洋">
<meta property="og:description" content="平常在项目中可能都会用到排序，就我本人而言，可能大部分都是用的选择排序或者冒泡排序，简单粗暴，但是这往往都只是实现了功能，而没有去关注性能，所以还是有必要了解常用的排序方法(使用内存)。
1.插入排序-直接插入排序基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要">
<meta property="og:image" content="http://html-js.site/images/page/sort/1.jpg">
<meta property="og:image" content="http://html-js.site/images/page/sort/2.jpg">
<meta property="og:image" content="http://html-js.site/images/page/sort/3.jpg">
<meta property="og:image" content="http://html-js.site/images/page/sort/4.jpg">
<meta property="og:image" content="http://html-js.site/images/page/sort/5.jpg">
<meta property="og:image" content="http://html-js.site/images/page/sort/6.jpg">
<meta property="og:updated_time" content="2016-06-08T06:14:04.788Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="排序算法">
<meta name="twitter:description" content="平常在项目中可能都会用到排序，就我本人而言，可能大部分都是用的选择排序或者冒泡排序，简单粗暴，但是这往往都只是实现了功能，而没有去关注性能，所以还是有必要了解常用的排序方法(使用内存)。
1.插入排序-直接插入排序基本思想:将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。
要">
<meta name="twitter:image" content="http://html-js.site/images/page/sort/1.jpg">



<script type="text/javascript" id="hexo.configuration">
  var NexT = window.NexT || {};
  var CONFIG = {
    scheme: 'Pisces',
    sidebar: {"position":"left","display":"post"},
    fancybox: true,
    motion: true,
    duoshuo: {
      userId: 0,
      author: '博主'
    }
  };
</script>




  <link rel="canonical" href="http://html-js.site/2016/05/20/排序算法/"/>

  <title> 排序算法 | 前端-洋洋 </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  



  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "//hm.baidu.com/hm.js?ca98d1db5559cb59848d14443c7fa5dd";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>








  
  
    
  

  <div class="container one-collumn sidebar-position-left page-post-detail ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">前端-洋洋</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
  <p class="site-subtitle">专注于前端</p>
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      

      
    </ul>
  

  
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            

  <div id="posts" class="posts-expand">
    

  
  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                排序算法
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            <span class="post-meta-item-icon">
              <i class="fa fa-calendar-o"></i>
            </span>
            <span class="post-meta-item-text">发表于</span>
            <time itemprop="dateCreated" datetime="2016-05-20T10:59:52+08:00" content="2016-05-20">
              2016-05-20
            </time>
          </span>

          

          
            
              <span class="post-comments-count">
                &nbsp; | &nbsp;
                <a href="/2016/05/20/排序算法/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count ds-thread-count" data-thread-key="2016/05/20/排序算法/" itemprop="commentsCount"></span>
                </a>
              </span>
            
          

          

          
          

          
        </div>
      </header>
    


    <div class="post-body" itemprop="articleBody">

      
      

      
        <p>平常在项目中可能都会用到排序，就我本人而言，可能大部分都是用的选择排序或者冒泡排序，简单粗暴，但是这往往都只是实现了功能，而没有去关注性能，所以还是有必要了解常用的排序方法(<b>使用内存</b>)。</p>
<h2 id="1-插入排序-直接插入排序"><a href="#1-插入排序-直接插入排序" class="headerlink" title="1.插入排序-直接插入排序"></a>1.插入排序-直接插入排序</h2><h3 id="基本思想"><a href="#基本思想" class="headerlink" title="基本思想:"></a>基本思想:</h3><p>将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。</p>
<h3 id="要点："><a href="#要点：" class="headerlink" title="要点："></a>要点：</h3><p>设立哨兵，作为临时存储和判断数组边界之用。</p>
<h3 id="直接插入排序示例："><a href="#直接插入排序示例：" class="headerlink" title="直接插入排序示例："></a>直接插入排序示例：</h3><p><img width="500" src="/images/page/sort/1.jpg"></p>
<p>如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，<b>所以插入排序是稳定的。</b></p>
<h3 id="原理演示："><a href="#原理演示：" class="headerlink" title="原理演示："></a>原理演示：</h3><p><a href="/file/sortAnimate/index.html" target="_blank">点击查看</a></p>
<h3 id="算法实现："><a href="#算法实现：" class="headerlink" title="算法实现："></a>算法实现：</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">function insertSortArray(sort_Array,x)&#123;         //一趟排序的算法</span><br><span class="line">for(var i=0;i&lt;sort_Array.length;i++)&#123;</span><br><span class="line">   if(sort_array[i]&gt;=x)&#123;                    //找到插入点</span><br><span class="line">    for (var j=sort_array.length; j&gt;i; j--)&#123;   //后挪空出位置 </span><br><span class="line">     sort_array[j]=sort_array[j-1]         </span><br><span class="line">    &#125;</span><br><span class="line">    sort_array[i]=x;                             //插入</span><br><span class="line">    break;                                      //任务结束，退出循环</span><br><span class="line">   &#125;</span><br><span class="line">&#125;</span><br><span class="line">return sort_array;                                      //返回处理后的数组</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line">function SortArrayByInsert(array)&#123;                      //主排序算法</span><br><span class="line">var returnValue=new Array(1);                        //定义成功排序后的返回值，初始大小为一位</span><br><span class="line">returnValue[0]=array[0];                               //在结果后置入排序前的第一位</span><br><span class="line">for (i=1; i&lt;array.length; i++)&#123;</span><br><span class="line">   returnValue=insertSortArray(returnValue,array[i]);     //调用一趟排序函数，从第二个元素开始，依次使用</span><br><span class="line">&#125;</span><br><span class="line">return returnValue;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="2-插入排序—希尔排序（Shell-s-Sort）"><a href="#2-插入排序—希尔排序（Shell-s-Sort）" class="headerlink" title="2.插入排序—希尔排序（Shell`s Sort）"></a>2.插入排序—希尔排序（Shell`s Sort）</h2><p>希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫<b>缩小增量排序</b></p>
<h3 id="基本思想："><a href="#基本思想：" class="headerlink" title="基本思想："></a>基本思想：</h3><p>先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。</p>
<h3 id="原理演示：-1"><a href="#原理演示：-1" class="headerlink" title="原理演示："></a>原理演示：</h3><p><a href="/file/sortAnimate/index.html" target="_blank">点击查看</a></p>
<h3 id="操作方法："><a href="#操作方法：" class="headerlink" title="操作方法："></a>操作方法：</h3><ul>
<li>选择一个增量序列t1，t2，…，tk，其中ti&gt;tj，tk=1；</li>
<li>按增量序列个数k，对序列进行k 趟排序；</li>
<li>每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。</li>
</ul>
<h3 id="示例："><a href="#示例：" class="headerlink" title="示例："></a>示例：</h3><p><img width="500" src="/images/page/sort/2.jpg"></p>
<h3 id="算法实现"><a href="#算法实现" class="headerlink" title="算法实现"></a>算法实现</h3><p>我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 …..1} n为要排序数的个数</p>
<p>即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line">function shellInsertSort(elements, di)&#123;</span><br><span class="line">  //从增量的所在位置开始</span><br><span class="line">  for(var i = di; i &lt; elements.length; i++)&#123;</span><br><span class="line">    //升序</span><br><span class="line">    if(elements[i] &lt; elements[i-di])&#123;</span><br><span class="line">      //取出增量位置的元素作为被插入元素（哨兵）</span><br><span class="line">      var guard = elements[i];</span><br><span class="line">      var j = i - di;</span><br><span class="line">      elements[i] = elements[j];</span><br><span class="line">      </span><br><span class="line">      //向前，将增量的倍数的位置作为同一组比较及进行直接插入法</span><br><span class="line">      while(j &gt;= 0 &amp;&amp; guard &lt; elements[j])&#123;</span><br><span class="line">        elements[j+di] = elements[j];</span><br><span class="line">        j -= di;</span><br><span class="line">      &#125;</span><br><span class="line">      </span><br><span class="line">      //插入</span><br><span class="line">      elements[j + di] = guard;</span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">function shellSort(elements)&#123;</span><br><span class="line">  //增量为序列的一半</span><br><span class="line">  var di = parseInt(elements.length / 2);</span><br><span class="line">  while(di &gt;= 1)&#123;</span><br><span class="line">    shellInsertSort(elements, di);</span><br><span class="line">    //每次减半，最后增量必须为1</span><br><span class="line">    di = parseInt(di / 2);</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">var elements = [10, 9, 8, 7, 6, 5];</span><br><span class="line">console.log(&apos;before: &apos; + elements);</span><br><span class="line">shellSort(elements);</span><br><span class="line">console.log(&apos; after: &apos; + elements);</span><br></pre></td></tr></table></figure>
<p>效率：比直接插入法快。但不是一种稳定的排序算法，关键取决于增量的选择，初次通常选取序列长度的一半。</p>
<h2 id="3-选择排序—简单选择排序（Simple-Selection-Sort）"><a href="#3-选择排序—简单选择排序（Simple-Selection-Sort）" class="headerlink" title="3.选择排序—简单选择排序（Simple Selection Sort）"></a>3.选择排序—简单选择排序（Simple Selection Sort）</h2><h3 id="基本思想：-1"><a href="#基本思想：-1" class="headerlink" title="基本思想："></a>基本思想：</h3><p>在要排序的一组数中，选出最小（或者最大）的一个数与<b style="color:green">第1个位置</b>的数交换；然后在剩下的数当中再找最小（或者最大）的与<b style="color:green">第2个位置</b>的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。</p>
<h3 id="简单选择排序的示例"><a href="#简单选择排序的示例" class="headerlink" title="简单选择排序的示例"></a>简单选择排序的示例</h3><p><img width="500" src="/images/page/sort/3.jpg"></p>
<h3 id="原理演示：-2"><a href="#原理演示：-2" class="headerlink" title="原理演示："></a>原理演示：</h3><p><a href="/file/sortAnimate/index.html" target="_blank">点击查看</a></p>
<h3 id="操作方法：-1"><a href="#操作方法：-1" class="headerlink" title="操作方法："></a>操作方法：</h3><p>第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；</p>
<p>第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；</p>
<p>以此类推…..</p>
<p>第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，</p>
<p>直到整个序列按关键码有序。</p>
<h3 id="算法实现-1"><a href="#算法实现-1" class="headerlink" title="算法实现"></a>算法实现</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">function sorrt(ary) &#123;</span><br><span class="line">    length = ary.length;</span><br><span class="line">    for (var i = 0; i &lt; length; i++) &#123;</span><br><span class="line">        _min = ary[i]</span><br><span class="line">        k = i</span><br><span class="line">        for (var j = i + 1; j &lt; length; j++) &#123;</span><br><span class="line">            if (_min &gt; ary[j]) &#123;</span><br><span class="line">                _min = ary[j]</span><br><span class="line">                k = j</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        ary[k] = ary[i]</span><br><span class="line">        ary[i] = _min</span><br><span class="line">    &#125;</span><br><span class="line">    return ary;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>简单选择排序的改进——二元选择排序</p>
<p>简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。</p>
<h2 id="4-交换排序—冒泡排序（Bubble-Sort）"><a href="#4-交换排序—冒泡排序（Bubble-Sort）" class="headerlink" title="4. 交换排序—冒泡排序（Bubble Sort）"></a>4. 交换排序—冒泡排序（Bubble Sort）</h2><h3 id="基本思想：-2"><a href="#基本思想：-2" class="headerlink" title="基本思想："></a>基本思想：</h3><p>在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。</p>
<h3 id="冒泡排序的示例"><a href="#冒泡排序的示例" class="headerlink" title="冒泡排序的示例"></a>冒泡排序的示例</h3><p><img width="500" src="/images/page/sort/4.jpg"></p>
<h3 id="原理演示：-3"><a href="#原理演示：-3" class="headerlink" title="原理演示："></a>原理演示：</h3><p><a href="/file/sortAnimate/index.html" target="_blank">点击查看</a></p>
<h3 id="算法的实现："><a href="#算法的实现：" class="headerlink" title="算法的实现："></a>算法的实现：</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">void bubbleSort(int a[], int n)&#123;</span><br><span class="line">	for(int i =0 ; i&lt; n-1; ++i) &#123;</span><br><span class="line">		for(int j = 0; j &lt; n-i-1; ++j) &#123;</span><br><span class="line">			if(a[j] &gt; a[j+1])</span><br><span class="line">			&#123;</span><br><span class="line">				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="冒泡排序算法的改进"><a href="#冒泡排序算法的改进" class="headerlink" title="冒泡排序算法的改进"></a>冒泡排序算法的改进</h3><p>对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。</p>
<h2 id="5-交换排序—快速排序（Quick-Sort）"><a href="#5-交换排序—快速排序（Quick-Sort）" class="headerlink" title="5. 交换排序—快速排序（Quick Sort）"></a>5. 交换排序—快速排序（Quick Sort）</h2><h3 id="基本思想-1"><a href="#基本思想-1" class="headerlink" title="基本思想"></a>基本思想</h3><p>1）选择一个基准元素,通常选择第一个元素或者最后一个元素,</p>
<p>2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。</p>
<p>3）此时基准元素在其排好序后的正确位置</p>
<p>4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。</p>
<h3 id="原理演示：-4"><a href="#原理演示：-4" class="headerlink" title="原理演示："></a>原理演示：</h3><p><a href="/file/sortAnimate/index.html" target="_blank">点击查看</a></p>
<h3 id="快速排序的示例："><a href="#快速排序的示例：" class="headerlink" title="快速排序的示例："></a>快速排序的示例：</h3><p>（a）一趟排序的过程：<br><img width="500" src="/images/page/sort/5.jpg"><br>（b）排序的全过程<br><img width="500" src="/images/page/sort/6.jpg"></p>
<h3 id="算法的实现：-1"><a href="#算法的实现：-1" class="headerlink" title="算法的实现："></a>算法的实现：</h3><p> 递归实现：<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line">void print(int a[], int n)&#123;  </span><br><span class="line">    for(int j= 0; j&lt;n; j++)&#123;  </span><br><span class="line">        cout&lt;&lt;a[j] &lt;&lt;&quot;  &quot;;  </span><br><span class="line">    &#125;  </span><br><span class="line">    cout&lt;&lt;endl;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line">void swap(int *a, int *b)  </span><br><span class="line">&#123;  </span><br><span class="line">    int tmp = *a;  </span><br><span class="line">    *a = *b;  </span><br><span class="line">    *b = tmp;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line">int partition(int a[], int low, int high)  </span><br><span class="line">&#123;  </span><br><span class="line">    int privotKey = a[low];                             //基准元素  </span><br><span class="line">    while(low &lt; high)&#123;                                   //从表的两端交替地向中间扫描  </span><br><span class="line">        while(low &lt; high  &amp;&amp; a[high] &gt;= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  </span><br><span class="line">        swap(&amp;a[low], &amp;a[high]);  </span><br><span class="line">        while(low &lt; high  &amp;&amp; a[low] &lt;= privotKey ) ++low;  </span><br><span class="line">        swap(&amp;a[low], &amp;a[high]);  </span><br><span class="line">    &#125;  </span><br><span class="line">    print(a,10);  </span><br><span class="line">    return low;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line">  </span><br><span class="line">void quickSort(int a[], int low, int high)&#123;  </span><br><span class="line">    if(low &lt; high)&#123;  </span><br><span class="line">        int privotLoc = partition(a,  low,  high);  //将表一分为二  </span><br><span class="line">        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  </span><br><span class="line">        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line">int main()&#123;  </span><br><span class="line">    int a[10] = &#123;3,1,5,7,2,4,9,6,10,8&#125;;  </span><br><span class="line">    cout&lt;&lt;&quot;初始值：&quot;;  </span><br><span class="line">    print(a,10);  </span><br><span class="line">    quickSort(a,0,9);  </span><br><span class="line">    cout&lt;&lt;&quot;结果：&quot;;  </span><br><span class="line">    print(a,10);  </span><br><span class="line">  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h3 id="分析："><a href="#分析：" class="headerlink" title="分析："></a>分析：</h3><p>快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。</p>
<h3 id="快速排序的改进"><a href="#快速排序的改进" class="headerlink" title="快速排序的改进"></a>快速排序的改进</h3><p>在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。</p>
<p>快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；</p>

      
    </div>

    <div>
      
        

      
    </div>

    <div>
      
        
  <div style="padding: 10px 0; margin: 20px auto; width: 90%; text-align: center;">
    <div>坚持原创技术分享，您的支持将鼓励我继续创作！</div>
    <button id="rewardButton" disable="enable" onclick="var qr = document.getElementById('QR'); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}">
      <span>赏</span>
    </button>
    <div id="QR" style="display: none;">
      
        <div id="wechat" style="display: inline-block">
          <img id="wechat_qr" src="/wechat.jpg" alt="wangyang WeChat Pay"/>
          <p>微信打赏</p>
        </div>
      
      
        <div id="alipay" style="display: inline-block">
          <img id="alipay_qr" src="/alipay.jpg" alt="wangyang Alipay"/>
          <p>支付宝打赏</p>
        </div>
      
    </div>
  </div>


      
    </div>

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/排序/" rel="tag">#排序</a>
          
            <a href="/tags/算法/" rel="tag">#算法</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/2016/05/10/Flex布局/" rel="next" title="Flex布局">
                <i class="fa fa-chevron-left"></i> Flex布局
              </a>
            
          </div>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/2016/05/30/移动端适配方案/" rel="prev" title="移动端适配方案">
                移动端适配方案 <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
    </div>
  </div>


          </div>
          


          
  <div class="comments" id="comments">
    
      <div class="ds-thread" data-thread-key="2016/05/20/排序算法/"
           data-title="排序算法" data-url="http://html-js.site/2016/05/20/排序算法/">
      </div>
    
  </div>


        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            站点概览
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel ">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" itemprop="image"
               src="/default_avatar.jpg"
               alt="wangyang" />
          <p class="site-author-name" itemprop="name">wangyang</p>
          <p class="site-description motion-element" itemprop="description">专注于前端</p>
        </div>
        <nav class="site-state motion-element">
          <div class="site-state-item site-state-posts">
            <a href="/archives">
              <span class="site-state-item-count">15</span>
              <span class="site-state-item-name">日志</span>
            </a>
          </div>

          

          
            <div class="site-state-item site-state-tags">
              <a href="/tags">
                <span class="site-state-item-count">23</span>
                <span class="site-state-item-name">标签</span>
              </a>
            </div>
          

        </nav>

        
          <div class="feed-link motion-element">
            <a href="/atom.xml" rel="alternate">
              <i class="fa fa-rss"></i>
              RSS
            </a>
          </div>
        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="https://github.com/WangYang-Rex" target="_blank" title="GitHub">
                  
                    <i class="fa fa-fw fa-github"></i>
                  
                  GitHub
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://weibo.com/u/2690568063/" target="_blank" title="Weibo">
                  
                    <i class="fa fa-fw fa-weibo"></i>
                  
                  Weibo
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="617418875" target="_blank" title="QQ">
                  
                    <i class="fa fa-fw fa-qq"></i>
                  
                  QQ
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="mailto:617418875@qq.com" target="_blank" title="Mail">
                  
                    <i class="fa fa-fw fa-envelope-o"></i>
                  
                  Mail
                </a>
              </span>
            
          
        </div>

        
        

        
        
          <div class="links-of-blogroll motion-element links-of-blogroll-inline">
            <div class="links-of-blogroll-title">
              <i class="fa  fa-fw fa-globe"></i>
              友链
            </div>
            <ul class="links-of-blogroll-list">
              
                <li class="links-of-blogroll-item">
                  <a href="http://http://moshui.site/" title="moxhuis" target="_blank">moxhuis</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://indexof.site/" title="indexof" target="_blank">indexof</a>
                </li>
              
                <li class="links-of-blogroll-item">
                  <a href="http://xiaoqiang730730.github.io/" title="xiaoqiang" target="_blank">xiaoqiang</a>
                </li>
              
            </ul>
          </div>
        

      </section>

      
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">
            
              
            
            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#1-插入排序-直接插入排序"><span class="nav-number">1.</span> <span class="nav-text">1.插入排序-直接插入排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#基本思想"><span class="nav-number">1.1.</span> <span class="nav-text">基本思想:</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#要点："><span class="nav-number">1.2.</span> <span class="nav-text">要点：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#直接插入排序示例："><span class="nav-number">1.3.</span> <span class="nav-text">直接插入排序示例：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#原理演示："><span class="nav-number">1.4.</span> <span class="nav-text">原理演示：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法实现："><span class="nav-number">1.5.</span> <span class="nav-text">算法实现：</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-插入排序—希尔排序（Shell-s-Sort）"><span class="nav-number">2.</span> <span class="nav-text">2.插入排序—希尔排序（Shell`s Sort）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#基本思想："><span class="nav-number">2.1.</span> <span class="nav-text">基本思想：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#原理演示：-1"><span class="nav-number">2.2.</span> <span class="nav-text">原理演示：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#操作方法："><span class="nav-number">2.3.</span> <span class="nav-text">操作方法：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#示例："><span class="nav-number">2.4.</span> <span class="nav-text">示例：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法实现"><span class="nav-number">2.5.</span> <span class="nav-text">算法实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-选择排序—简单选择排序（Simple-Selection-Sort）"><span class="nav-number">3.</span> <span class="nav-text">3.选择排序—简单选择排序（Simple Selection Sort）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#基本思想：-1"><span class="nav-number">3.1.</span> <span class="nav-text">基本思想：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#简单选择排序的示例"><span class="nav-number">3.2.</span> <span class="nav-text">简单选择排序的示例</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#原理演示：-2"><span class="nav-number">3.3.</span> <span class="nav-text">原理演示：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#操作方法：-1"><span class="nav-number">3.4.</span> <span class="nav-text">操作方法：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法实现-1"><span class="nav-number">3.5.</span> <span class="nav-text">算法实现</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#4-交换排序—冒泡排序（Bubble-Sort）"><span class="nav-number">4.</span> <span class="nav-text">4. 交换排序—冒泡排序（Bubble Sort）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#基本思想：-2"><span class="nav-number">4.1.</span> <span class="nav-text">基本思想：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#冒泡排序的示例"><span class="nav-number">4.2.</span> <span class="nav-text">冒泡排序的示例</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#原理演示：-3"><span class="nav-number">4.3.</span> <span class="nav-text">原理演示：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法的实现："><span class="nav-number">4.4.</span> <span class="nav-text">算法的实现：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#冒泡排序算法的改进"><span class="nav-number">4.5.</span> <span class="nav-text">冒泡排序算法的改进</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#5-交换排序—快速排序（Quick-Sort）"><span class="nav-number">5.</span> <span class="nav-text">5. 交换排序—快速排序（Quick Sort）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#基本思想-1"><span class="nav-number">5.1.</span> <span class="nav-text">基本思想</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#原理演示：-4"><span class="nav-number">5.2.</span> <span class="nav-text">原理演示：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#快速排序的示例："><span class="nav-number">5.3.</span> <span class="nav-text">快速排序的示例：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法的实现：-1"><span class="nav-number">5.4.</span> <span class="nav-text">算法的实现：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#分析："><span class="nav-number">5.5.</span> <span class="nav-text">分析：</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#快速排序的改进"><span class="nav-number">5.6.</span> <span class="nav-text">快速排序的改进</span></a></li></ol></li></ol></div>
            
          </div>
        </section>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  
  &copy; 
  <span itemprop="copyrightYear">2016</span>
  <span class="with-love">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">wangyang</span>
</div>

<div class="powered-by">
  由 <a class="theme-link" href="https://hexo.io">Hexo</a> 强力驱动
</div>

<div class="theme-info">
  主题 -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT.Pisces
  </a>
</div>

        

        
      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  



  
  <script type="text/javascript" src="/vendors/jquery/index.js?v=2.1.3"></script>

  
  <script type="text/javascript" src="/vendors/fastclick/lib/fastclick.min.js?v=1.0.6"></script>

  
  <script type="text/javascript" src="/vendors/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  <script type="text/javascript" src="/vendors/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/vendors/velocity/velocity.ui.min.js?v=1.2.1"></script>

  
  <script type="text/javascript" src="/vendors/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.0.1"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.0.1"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.0.1"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.0.1"></script>



  
  <script type="text/javascript" src="/js/src/scrollspy.js?v=5.0.1"></script>
<script type="text/javascript" src="/js/src/post-details.js?v=5.0.1"></script>



  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.0.1"></script>



  

  
    
  

  <script type="text/javascript">
    var duoshuoQuery = {short_name:"html-js"};
    (function() {
      var ds = document.createElement('script');
      ds.type = 'text/javascript';ds.async = true;
      ds.id = 'duoshuo-script';
      ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js';
      ds.charset = 'UTF-8';
      (document.getElementsByTagName('head')[0]
      || document.getElementsByTagName('body')[0]).appendChild(ds);
    })();
  </script>

  
    
    <script src="/vendors/ua-parser-js/dist/ua-parser.min.js?v=0.7.9"></script>
    <script src="/js/src/hook-duoshuo.js"></script>
  






  
  

  

  

  

</body>
</html>
